package com.arron.algorithm.leetcodetop100.数组;

import java.util.HashMap;
import java.util.Map;

public class 轮转数组 {




    // 翻转数组的方法:
    // 将
    public void rotate_plus(int[] nums, int k) {

        k %= nums.length;
        //先将整个数组翻转
        reverse(nums,0,nums.length-1);

        // 翻转 nums[0...k%len-1] 元素
        reverse(nums,0,k-1);
        // 翻转 nums[k%len...len-1] 元素
        reverse(nums,k,nums.length-1);

    }

    public void reverse(int[] nums,int start,int end){

        int left = start;
        int right = end;


        while (left<right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }

    }



    //  轮转数组
    // nums = [1,2,3,4,5,6,7], k = 3

    /**
     * 暴力解法
     *   时间复杂度 O(k*n)
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        if (k==0 || nums.length ==1){
            return;
        }
        int n = nums.length;
        Map<Integer,Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int index = (i+k)%n;
            indexMap.put(index,nums[i]);
        }
        for (int i = 0; i < n; i++) {
            nums[i] = indexMap.get(i);
        }
    }


}
